<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-comment">{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998

-}</span><span>
</span><span id="line-6"></span><span>
</span><span id="line-7"></span><span class="hs-pragma">{-# LANGUAGE CPP #-}</span><span>
</span><span id="line-8"></span><span>
</span><span id="line-9"></span><span class="hs-comment">-- | Set-like operations on lists</span><span>
</span><span id="line-10"></span><span class="hs-comment">--</span><span>
</span><span id="line-11"></span><span class="hs-comment">-- Avoid using them as much as possible</span><span>
</span><span id="line-12"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">GHC.Data.List.SetOps</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-13"></span><span>        </span><span class="annot"><a href="GHC.Data.List.SetOps.html#unionLists"><span class="hs-identifier">unionLists</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#minusList"><span class="hs-identifier">minusList</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-14"></span><span>
</span><span id="line-15"></span><span>        </span><span class="hs-comment">-- Association lists</span><span>
</span><span id="line-16"></span><span>        </span><span class="annot"><a href="GHC.Data.List.SetOps.html#Assoc"><span class="hs-identifier">Assoc</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#assoc"><span class="hs-identifier">assoc</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#assocMaybe"><span class="hs-identifier">assocMaybe</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#assocUsing"><span class="hs-identifier">assocUsing</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#assocDefault"><span class="hs-identifier">assocDefault</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#assocDefaultUsing"><span class="hs-identifier">assocDefaultUsing</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-17"></span><span>
</span><span id="line-18"></span><span>        </span><span class="hs-comment">-- Duplicate handling</span><span>
</span><span id="line-19"></span><span>        </span><span class="annot"><a href="GHC.Data.List.SetOps.html#hasNoDups"><span class="hs-identifier">hasNoDups</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#removeDups"><span class="hs-identifier">removeDups</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#findDupsEq"><span class="hs-identifier">findDupsEq</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-20"></span><span>        </span><span class="annot"><a href="GHC.Data.List.SetOps.html#equivClasses"><span class="hs-identifier">equivClasses</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-21"></span><span>
</span><span id="line-22"></span><span>        </span><span class="hs-comment">-- Indexing</span><span>
</span><span id="line-23"></span><span>        </span><span class="annot"><a href="GHC.Data.List.SetOps.html#getNth"><span class="hs-identifier">getNth</span></a></span><span>
</span><span id="line-24"></span><span>   </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span class="hs-cpp">

#include &quot;HsVersions.h&quot;
</span><span>
</span><span id="line-28"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Prelude.html"><span class="hs-identifier">GHC.Prelude</span></a></span><span>
</span><span id="line-29"></span><span>
</span><span id="line-30"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html"><span class="hs-identifier">GHC.Utils.Outputable</span></a></span><span>
</span><span id="line-31"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Utils.Misc.html"><span class="hs-identifier">GHC.Utils.Misc</span></a></span><span>
</span><span id="line-32"></span><span>
</span><span id="line-33"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../base/src/Data.List.html#"><span class="hs-identifier">Data.List</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">L</span></span><span>
</span><span id="line-34"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../base/src/Data.List.NonEmpty.html#"><span class="hs-identifier">Data.List.NonEmpty</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">NE</span></span><span>
</span><span id="line-35"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.List.NonEmpty.html#"><span class="hs-identifier">Data.List.NonEmpty</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Base.html#NonEmpty"><span class="hs-identifier">NonEmpty</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-36"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../containers/src/Data.Set.html#"><span class="hs-identifier">Data.Set</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">S</span></span><span>
</span><span id="line-37"></span><span>
</span><span id="line-38"></span><span id="local-6989586621680814865"><span class="annot"><a href="GHC.Data.List.SetOps.html#getNth"><span class="hs-identifier hs-type">getNth</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814865"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814865"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814865"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-39"></span><span id="getNth"><span class="annot"><span class="annottext">getNth :: forall a. Outputable a =&gt; [a] -&gt; Int -&gt; a
</span><a href="GHC.Data.List.SetOps.html#getNth"><span class="hs-identifier hs-var hs-var">getNth</span></a></span></span><span> </span><span id="local-6989586621680814772"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814772"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span id="local-6989586621680814771"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621680814771"><span class="hs-identifier hs-var">n</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">ASSERT2</span><span class="hs-special">(</span><span> </span><span class="hs-identifier">xs</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">lengthExceeds</span><span class="hs-special">`</span><span> </span><span class="hs-identifier">n</span><span class="hs-special">,</span><span> </span><span class="hs-identifier">ppr</span><span> </span><span class="hs-identifier">n</span><span> </span><span class="hs-operator">$$</span><span> </span><span class="hs-identifier">ppr</span><span> </span><span class="hs-identifier">xs</span><span> </span><span class="hs-special">)</span><span>
</span><span id="line-40"></span><span>             </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814772"><span class="hs-identifier hs-var">xs</span></a></span><span> </span><span class="annot"><span class="annottext">[a] -&gt; Int -&gt; a
forall a. [a] -&gt; Int -&gt; a
</span><a href="../../base/src/GHC.List.html#%21%21"><span class="hs-operator hs-var">!!</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621680814771"><span class="hs-identifier hs-var">n</span></a></span><span>
</span><span id="line-41"></span><span>
</span><span id="line-42"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
        Treating lists as sets
        Assumes the lists contain no duplicates, but are unordered
*                                                                      *
************************************************************************
-}</span><span>
</span><span id="line-50"></span><span>
</span><span id="line-51"></span><span>
</span><span id="line-52"></span><span class="hs-comment">-- | Assumes that the arguments contain no duplicates</span><span>
</span><span id="line-53"></span><span id="local-6989586621680814854"><span class="annot"><a href="GHC.Data.List.SetOps.html#unionLists"><span class="hs-identifier hs-type">unionLists</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Utils.Misc.html#HasDebugCallStack"><span class="hs-identifier hs-type">HasDebugCallStack</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814854"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680814854"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814854"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814854"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814854"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-54"></span><span class="hs-comment">-- We special case some reasonable common patterns.</span><span>
</span><span id="line-55"></span><span id="unionLists"><span class="annot"><span class="annottext">unionLists :: forall a.
(HasDebugCallStack, Outputable a, Eq a) =&gt;
[a] -&gt; [a] -&gt; [a]
</span><a href="GHC.Data.List.SetOps.html#unionLists"><span class="hs-identifier hs-var hs-var">unionLists</span></a></span></span><span> </span><span id="local-6989586621680814752"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814752"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814752"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-56"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#unionLists"><span class="hs-identifier hs-var">unionLists</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span id="local-6989586621680814751"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814751"><span class="hs-identifier hs-var">ys</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814751"><span class="hs-identifier hs-var">ys</span></a></span><span>
</span><span id="line-57"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#unionLists"><span class="hs-identifier hs-var">unionLists</span></a></span><span> </span><span class="hs-special">[</span><span id="local-6989586621680814750"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814750"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">]</span><span> </span><span id="local-6989586621680814749"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814749"><span class="hs-identifier hs-var">ys</span></a></span></span><span>
</span><span id="line-58"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">String -&gt; a -&gt; [a] -&gt; Bool
forall a. Eq a =&gt; String -&gt; a -&gt; [a] -&gt; Bool
</span><a href="GHC.Utils.Misc.html#isIn"><span class="hs-identifier hs-var">isIn</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;unionLists&quot;</span></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814750"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814749"><span class="hs-identifier hs-var">ys</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814749"><span class="hs-identifier hs-var">ys</span></a></span><span>
</span><span id="line-59"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814750"><span class="hs-identifier hs-var">x</span></a></span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; [a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814749"><span class="hs-identifier hs-var">ys</span></a></span><span>
</span><span id="line-60"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#unionLists"><span class="hs-identifier hs-var">unionLists</span></a></span><span> </span><span id="local-6989586621680814747"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814747"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-special">[</span><span id="local-6989586621680814746"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814746"><span class="hs-identifier hs-var">y</span></a></span></span><span class="hs-special">]</span><span>
</span><span id="line-61"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">String -&gt; a -&gt; [a] -&gt; Bool
forall a. Eq a =&gt; String -&gt; a -&gt; [a] -&gt; Bool
</span><a href="GHC.Utils.Misc.html#isIn"><span class="hs-identifier hs-var">isIn</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;unionLists&quot;</span></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814746"><span class="hs-identifier hs-var">y</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814747"><span class="hs-identifier hs-var">xs</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814747"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-62"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814746"><span class="hs-identifier hs-var">y</span></a></span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; [a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814747"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-63"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#unionLists"><span class="hs-identifier hs-var">unionLists</span></a></span><span> </span><span id="local-6989586621680814745"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814745"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span id="local-6989586621680814744"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814744"><span class="hs-identifier hs-var">ys</span></a></span></span><span>
</span><span id="line-64"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">WARN</span><span class="hs-special">(</span><span class="hs-identifier">lengthExceeds</span><span> </span><span class="hs-identifier">xs</span><span> </span><span class="hs-number">100</span><span> </span><span class="hs-operator">||</span><span> </span><span class="hs-identifier">lengthExceeds</span><span> </span><span class="hs-identifier">ys</span><span> </span><span class="hs-number">100</span><span class="hs-special">,</span><span> </span><span class="hs-identifier">ppr</span><span> </span><span class="hs-identifier">xs</span><span> </span><span class="hs-operator">$$</span><span> </span><span class="hs-identifier">ppr</span><span> </span><span class="hs-identifier">ys</span><span class="hs-special">)</span><span>
</span><span id="line-65"></span><span>    </span><span class="hs-special">[</span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814741"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="hs-glyph">|</span><span> </span><span id="local-6989586621680814741"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814741"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814745"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">String -&gt; a -&gt; [a] -&gt; Bool
forall a. Eq a =&gt; String -&gt; a -&gt; [a] -&gt; Bool
</span><a href="GHC.Utils.Misc.html#isn%27tIn"><span class="hs-identifier hs-var">isn'tIn</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;unionLists&quot;</span></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814741"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814744"><span class="hs-identifier hs-var">ys</span></a></span><span class="hs-special">]</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; [a] -&gt; [a]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814744"><span class="hs-identifier hs-var">ys</span></a></span><span>
</span><span id="line-66"></span><span>
</span><span id="line-67"></span><span class="hs-comment">-- | Calculate the set difference of two lists. This is</span><span>
</span><span id="line-68"></span><span class="hs-comment">-- /O((m + n) log n)/, where we subtract a list of /n/ elements</span><span>
</span><span id="line-69"></span><span class="hs-comment">-- from a list of /m/ elements.</span><span>
</span><span id="line-70"></span><span class="hs-comment">--</span><span>
</span><span id="line-71"></span><span class="hs-comment">-- Extremely short cases are handled specially:</span><span>
</span><span id="line-72"></span><span class="hs-comment">-- When /m/ or /n/ is 0, this takes /O(1)/ time. When /m/ is 1,</span><span>
</span><span id="line-73"></span><span class="hs-comment">-- it takes /O(n)/ time.</span><span>
</span><span id="line-74"></span><span id="local-6989586621680814845"><span class="annot"><a href="GHC.Data.List.SetOps.html#minusList"><span class="hs-identifier hs-type">minusList</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680814845"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814845"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814845"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814845"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-75"></span><span class="hs-comment">-- There's no point building a set to perform just one lookup, so we handle</span><span>
</span><span id="line-76"></span><span class="hs-comment">-- extremely short lists specially. It might actually be better to use</span><span>
</span><span id="line-77"></span><span class="hs-comment">-- an O(m*n) algorithm when m is a little longer (perhaps up to 4 or even 5).</span><span>
</span><span id="line-78"></span><span class="hs-comment">-- The tipping point will be somewhere in the area of where /m/ and /log n/</span><span>
</span><span id="line-79"></span><span class="hs-comment">-- become comparable, but we probably don't want to work too hard on this.</span><span>
</span><span id="line-80"></span><span id="minusList"><span class="annot"><span class="annottext">minusList :: forall a. Ord a =&gt; [a] -&gt; [a] -&gt; [a]
</span><a href="GHC.Data.List.SetOps.html#minusList"><span class="hs-identifier hs-var hs-var">minusList</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="annot"><span class="annottext">[a]
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-81"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#minusList"><span class="hs-identifier hs-var">minusList</span></a></span><span> </span><span id="local-6989586621680814731"><span class="annot"><span class="annottext">xs :: [a]
</span><a href="#local-6989586621680814731"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">[</span><span id="local-6989586621680814730"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814730"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">]</span><span> </span><span id="local-6989586621680814729"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814729"><span class="hs-identifier hs-var">ys</span></a></span></span><span>
</span><span id="line-82"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814730"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; Bool
forall (t :: * -&gt; *) a. (Foldable t, Eq a) =&gt; a -&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#elem"><span class="hs-operator hs-var">`elem`</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814729"><span class="hs-identifier hs-var">ys</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-83"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814731"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-84"></span><span class="hs-comment">-- Using an empty set or a singleton would also be silly, so let's not.</span><span>
</span><span id="line-85"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#minusList"><span class="hs-identifier hs-var">minusList</span></a></span><span> </span><span id="local-6989586621680814727"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814727"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814727"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-86"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#minusList"><span class="hs-identifier hs-var">minusList</span></a></span><span> </span><span id="local-6989586621680814726"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814726"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-special">[</span><span id="local-6989586621680814725"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814725"><span class="hs-identifier hs-var">y</span></a></span></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; Bool) -&gt; [a] -&gt; [a]
forall a. (a -&gt; Bool) -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#filter"><span class="hs-identifier hs-var">filter</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">/=</span></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814725"><span class="hs-identifier hs-var">y</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814726"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-87"></span><span class="hs-comment">-- When each list has at least two elements, we build a set from the</span><span>
</span><span id="line-88"></span><span class="hs-comment">-- second argument, allowing us to filter the first argument fairly</span><span>
</span><span id="line-89"></span><span class="hs-comment">-- efficiently.</span><span>
</span><span id="line-90"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#minusList"><span class="hs-identifier hs-var">minusList</span></a></span><span> </span><span id="local-6989586621680814723"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814723"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span id="local-6989586621680814722"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814722"><span class="hs-identifier hs-var">ys</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; Bool) -&gt; [a] -&gt; [a]
forall a. (a -&gt; Bool) -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#filter"><span class="hs-identifier hs-var">filter</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; Set a -&gt; Bool
forall a. Ord a =&gt; a -&gt; Set a -&gt; Bool
</span><a href="../../containers/src/Data.Set.Internal.html#notMember"><span class="hs-operator hs-var">`S.notMember`</span></a></span><span> </span><span class="annot"><span class="annottext">Set a
</span><a href="#local-6989586621680814720"><span class="hs-identifier hs-var">yss</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814723"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-91"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-92"></span><span>    </span><span id="local-6989586621680814720"><span class="annot"><span class="annottext">yss :: Set a
</span><a href="#local-6989586621680814720"><span class="hs-identifier hs-var hs-var">yss</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; Set a
forall a. Ord a =&gt; [a] -&gt; Set a
</span><a href="../../containers/src/Data.Set.Internal.html#fromList"><span class="hs-identifier hs-var">S.fromList</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814722"><span class="hs-identifier hs-var">ys</span></a></span><span>
</span><span id="line-93"></span><span>
</span><span id="line-94"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
\subsection[Utils-assoc]{Association lists}
*                                                                      *
************************************************************************

Inefficient finite maps based on association lists and equality.
-}</span><span>
</span><span id="line-103"></span><span>
</span><span id="line-104"></span><span class="hs-comment">-- A finite mapping based on equality and association lists</span><span>
</span><span id="line-105"></span><span class="hs-keyword">type</span><span> </span><span id="Assoc"><span class="annot"><a href="GHC.Data.List.SetOps.html#Assoc"><span class="hs-identifier hs-var">Assoc</span></a></span></span><span> </span><span id="local-6989586621680814717"><span class="annot"><a href="#local-6989586621680814717"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span id="local-6989586621680814716"><span class="annot"><a href="#local-6989586621680814716"><span class="hs-identifier hs-type">b</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680814717"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span class="annot"><a href="#local-6989586621680814716"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span>
</span><span id="line-106"></span><span>
</span><span id="line-107"></span><span id="local-6989586621680814829"><span id="local-6989586621680814830"><span class="annot"><a href="GHC.Data.List.SetOps.html#assoc"><span class="hs-identifier hs-type">assoc</span></a></span><span>             </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680814830"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#String"><span class="hs-identifier hs-type">String</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#Assoc"><span class="hs-identifier hs-type">Assoc</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814830"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814829"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814830"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814829"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-108"></span><span id="local-6989586621680814824"><span id="local-6989586621680814825"><span class="annot"><a href="GHC.Data.List.SetOps.html#assocDefault"><span class="hs-identifier hs-type">assocDefault</span></a></span><span>      </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680814825"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814824"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#Assoc"><span class="hs-identifier hs-type">Assoc</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814825"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814824"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814825"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814824"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-109"></span><span id="local-6989586621680814820"><span id="local-6989586621680814821"><span class="annot"><a href="GHC.Data.List.SetOps.html#assocUsing"><span class="hs-identifier hs-type">assocUsing</span></a></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680814821"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814821"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#String"><span class="hs-identifier hs-type">String</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#Assoc"><span class="hs-identifier hs-type">Assoc</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814821"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814820"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814821"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814820"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-110"></span><span id="local-6989586621680814816"><span id="local-6989586621680814817"><span class="annot"><a href="GHC.Data.List.SetOps.html#assocMaybe"><span class="hs-identifier hs-type">assocMaybe</span></a></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680814817"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#Assoc"><span class="hs-identifier hs-type">Assoc</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814817"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814816"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814817"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814816"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-111"></span><span id="local-6989586621680814834"><span id="local-6989586621680814835"><span class="annot"><a href="GHC.Data.List.SetOps.html#assocDefaultUsing"><span class="hs-identifier hs-type">assocDefaultUsing</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680814835"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814835"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814834"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.List.SetOps.html#Assoc"><span class="hs-identifier hs-type">Assoc</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814835"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814834"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814835"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814834"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-112"></span><span>
</span><span id="line-113"></span><span id="assocDefaultUsing"><span class="annot"><span class="annottext">assocDefaultUsing :: forall a b. (a -&gt; a -&gt; Bool) -&gt; b -&gt; Assoc a b -&gt; a -&gt; b
</span><a href="GHC.Data.List.SetOps.html#assocDefaultUsing"><span class="hs-identifier hs-var hs-var">assocDefaultUsing</span></a></span></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><span class="hs-identifier">_</span></span><span>  </span><span id="local-6989586621680814715"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680814715"><span class="hs-identifier hs-var">deflt</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>             </span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span>   </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680814715"><span class="hs-identifier hs-var">deflt</span></a></span><span>
</span><span id="line-114"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#assocDefaultUsing"><span class="hs-identifier hs-var">assocDefaultUsing</span></a></span><span> </span><span id="local-6989586621680814714"><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814714"><span class="hs-identifier hs-var">eq</span></a></span></span><span> </span><span id="local-6989586621680814713"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680814713"><span class="hs-identifier hs-var">deflt</span></a></span></span><span> </span><span class="hs-special">(</span><span class="hs-special">(</span><span id="local-6989586621680814712"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814712"><span class="hs-identifier hs-var">k</span></a></span></span><span class="hs-special">,</span><span id="local-6989586621680814711"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680814711"><span class="hs-identifier hs-var">v</span></a></span></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span> </span><span id="local-6989586621680814710"><span class="annot"><span class="annottext">[(a, b)]
</span><a href="#local-6989586621680814710"><span class="hs-identifier hs-var">rest</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621680814709"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814709"><span class="hs-identifier hs-var">key</span></a></span></span><span>
</span><span id="line-115"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814712"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814714"><span class="hs-operator hs-var">`eq`</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814709"><span class="hs-identifier hs-var">key</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680814711"><span class="hs-identifier hs-var">v</span></a></span><span>
</span><span id="line-116"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Bool) -&gt; b -&gt; [(a, b)] -&gt; a -&gt; b
forall a b. (a -&gt; a -&gt; Bool) -&gt; b -&gt; Assoc a b -&gt; a -&gt; b
</span><a href="GHC.Data.List.SetOps.html#assocDefaultUsing"><span class="hs-identifier hs-var">assocDefaultUsing</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814714"><span class="hs-identifier hs-var">eq</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680814713"><span class="hs-identifier hs-var">deflt</span></a></span><span> </span><span class="annot"><span class="annottext">[(a, b)]
</span><a href="#local-6989586621680814710"><span class="hs-identifier hs-var">rest</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814709"><span class="hs-identifier hs-var">key</span></a></span><span>
</span><span id="line-117"></span><span>
</span><span id="line-118"></span><span id="assoc"><span class="annot"><span class="annottext">assoc :: forall a b. Eq a =&gt; String -&gt; Assoc a b -&gt; a -&gt; b
</span><a href="GHC.Data.List.SetOps.html#assoc"><span class="hs-identifier hs-var hs-var">assoc</span></a></span></span><span> </span><span id="local-6989586621680814706"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621680814706"><span class="hs-identifier hs-var">crash_msg</span></a></span></span><span>         </span><span id="local-6989586621680814705"><span class="annot"><span class="annottext">Assoc a b
</span><a href="#local-6989586621680814705"><span class="hs-identifier hs-var">list</span></a></span></span><span> </span><span id="local-6989586621680814704"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814704"><span class="hs-identifier hs-var">key</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Bool) -&gt; b -&gt; Assoc a b -&gt; a -&gt; b
forall a b. (a -&gt; a -&gt; Bool) -&gt; b -&gt; Assoc a b -&gt; a -&gt; b
</span><a href="GHC.Data.List.SetOps.html#assocDefaultUsing"><span class="hs-identifier hs-var">assocDefaultUsing</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">(==)</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String -&gt; b
forall a. String -&gt; a
</span><a href="GHC.Utils.Panic.Plain.html#panic"><span class="hs-identifier hs-var">panic</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;Failed in assoc: &quot;</span></span><span> </span><span class="annot"><span class="annottext">String -&gt; String -&gt; String
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621680814706"><span class="hs-identifier hs-var">crash_msg</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Assoc a b
</span><a href="#local-6989586621680814705"><span class="hs-identifier hs-var">list</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814704"><span class="hs-identifier hs-var">key</span></a></span><span>
</span><span id="line-119"></span><span id="assocDefault"><span class="annot"><span class="annottext">assocDefault :: forall a b. Eq a =&gt; b -&gt; Assoc a b -&gt; a -&gt; b
</span><a href="GHC.Data.List.SetOps.html#assocDefault"><span class="hs-identifier hs-var hs-var">assocDefault</span></a></span></span><span> </span><span id="local-6989586621680814700"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680814700"><span class="hs-identifier hs-var">deflt</span></a></span></span><span>      </span><span id="local-6989586621680814699"><span class="annot"><span class="annottext">Assoc a b
</span><a href="#local-6989586621680814699"><span class="hs-identifier hs-var">list</span></a></span></span><span> </span><span id="local-6989586621680814698"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814698"><span class="hs-identifier hs-var">key</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Bool) -&gt; b -&gt; Assoc a b -&gt; a -&gt; b
forall a b. (a -&gt; a -&gt; Bool) -&gt; b -&gt; Assoc a b -&gt; a -&gt; b
</span><a href="GHC.Data.List.SetOps.html#assocDefaultUsing"><span class="hs-identifier hs-var">assocDefaultUsing</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">(==)</span></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680814700"><span class="hs-identifier hs-var">deflt</span></a></span><span> </span><span class="annot"><span class="annottext">Assoc a b
</span><a href="#local-6989586621680814699"><span class="hs-identifier hs-var">list</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814698"><span class="hs-identifier hs-var">key</span></a></span><span>
</span><span id="line-120"></span><span id="assocUsing"><span class="annot"><span class="annottext">assocUsing :: forall a b. (a -&gt; a -&gt; Bool) -&gt; String -&gt; Assoc a b -&gt; a -&gt; b
</span><a href="GHC.Data.List.SetOps.html#assocUsing"><span class="hs-identifier hs-var hs-var">assocUsing</span></a></span></span><span> </span><span id="local-6989586621680814697"><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814697"><span class="hs-identifier hs-var">eq</span></a></span></span><span> </span><span id="local-6989586621680814696"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621680814696"><span class="hs-identifier hs-var">crash_msg</span></a></span></span><span> </span><span id="local-6989586621680814695"><span class="annot"><span class="annottext">Assoc a b
</span><a href="#local-6989586621680814695"><span class="hs-identifier hs-var">list</span></a></span></span><span> </span><span id="local-6989586621680814694"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814694"><span class="hs-identifier hs-var">key</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Bool) -&gt; b -&gt; Assoc a b -&gt; a -&gt; b
forall a b. (a -&gt; a -&gt; Bool) -&gt; b -&gt; Assoc a b -&gt; a -&gt; b
</span><a href="GHC.Data.List.SetOps.html#assocDefaultUsing"><span class="hs-identifier hs-var">assocDefaultUsing</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814697"><span class="hs-identifier hs-var">eq</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String -&gt; b
forall a. String -&gt; a
</span><a href="GHC.Utils.Panic.Plain.html#panic"><span class="hs-identifier hs-var">panic</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;Failed in assoc: &quot;</span></span><span> </span><span class="annot"><span class="annottext">String -&gt; String -&gt; String
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621680814696"><span class="hs-identifier hs-var">crash_msg</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Assoc a b
</span><a href="#local-6989586621680814695"><span class="hs-identifier hs-var">list</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814694"><span class="hs-identifier hs-var">key</span></a></span><span>
</span><span id="line-121"></span><span>
</span><span id="line-122"></span><span id="assocMaybe"><span class="annot"><span class="annottext">assocMaybe :: forall a b. Eq a =&gt; Assoc a b -&gt; a -&gt; Maybe b
</span><a href="GHC.Data.List.SetOps.html#assocMaybe"><span class="hs-identifier hs-var hs-var">assocMaybe</span></a></span></span><span> </span><span id="local-6989586621680814692"><span class="annot"><span class="annottext">Assoc a b
</span><a href="#local-6989586621680814692"><span class="hs-identifier hs-var">alist</span></a></span></span><span> </span><span id="local-6989586621680814691"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814691"><span class="hs-identifier hs-var">key</span></a></span></span><span>
</span><span id="line-123"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Assoc a b -&gt; Maybe b
forall {a}. [(a, a)] -&gt; Maybe a
</span><a href="#local-6989586621680814690"><span class="hs-identifier hs-var">lookup</span></a></span><span> </span><span class="annot"><span class="annottext">Assoc a b
</span><a href="#local-6989586621680814692"><span class="hs-identifier hs-var">alist</span></a></span><span>
</span><span id="line-124"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-125"></span><span>    </span><span id="local-6989586621680814690"><span class="annot"><span class="annottext">lookup :: [(a, a)] -&gt; Maybe a
</span><a href="#local-6989586621680814690"><span class="hs-identifier hs-var hs-var">lookup</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>             </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Maybe a
forall a. Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span>
</span><span id="line-126"></span><span>    </span><span class="annot"><a href="#local-6989586621680814690"><span class="hs-identifier hs-var">lookup</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-special">(</span><span id="local-6989586621680814688"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814688"><span class="hs-identifier hs-var">tv</span></a></span></span><span class="hs-special">,</span><span id="local-6989586621680814687"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814687"><span class="hs-identifier hs-var">ty</span></a></span></span><span class="hs-special">)</span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span id="local-6989586621680814686"><span class="annot"><span class="annottext">[(a, a)]
</span><a href="#local-6989586621680814686"><span class="hs-identifier hs-var">rest</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">if</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814691"><span class="hs-identifier hs-var">key</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">==</span></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814688"><span class="hs-identifier hs-var">tv</span></a></span><span> </span><span class="hs-keyword">then</span><span> </span><span class="annot"><span class="annottext">a -&gt; Maybe a
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814687"><span class="hs-identifier hs-var">ty</span></a></span><span> </span><span class="hs-keyword">else</span><span> </span><span class="annot"><span class="annottext">[(a, a)] -&gt; Maybe a
</span><a href="#local-6989586621680814690"><span class="hs-identifier hs-var">lookup</span></a></span><span> </span><span class="annot"><span class="annottext">[(a, a)]
</span><a href="#local-6989586621680814686"><span class="hs-identifier hs-var">rest</span></a></span><span>
</span><span id="line-127"></span><span>
</span><span id="line-128"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
\subsection[Utils-dups]{Duplicate-handling}
*                                                                      *
************************************************************************
-}</span><span>
</span><span id="line-135"></span><span>
</span><span id="line-136"></span><span id="local-6989586621680814812"><span class="annot"><a href="GHC.Data.List.SetOps.html#hasNoDups"><span class="hs-identifier hs-type">hasNoDups</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621680814812"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814812"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span></span><span>
</span><span id="line-137"></span><span>
</span><span id="line-138"></span><span id="hasNoDups"><span class="annot"><span class="annottext">hasNoDups :: forall a. Eq a =&gt; [a] -&gt; Bool
</span><a href="GHC.Data.List.SetOps.html#hasNoDups"><span class="hs-identifier hs-var hs-var">hasNoDups</span></a></span></span><span> </span><span id="local-6989586621680814684"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814684"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; [a] -&gt; Bool
</span><a href="#local-6989586621680814683"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814684"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-139"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-140"></span><span>    </span><span id="local-6989586621680814683"><span class="annot"><span class="annottext">f :: [a] -&gt; [a] -&gt; Bool
</span><a href="#local-6989586621680814683"><span class="hs-identifier hs-var hs-var">f</span></a></span></span><span> </span><span class="annot"><span class="annottext">[a]
</span><span class="hs-identifier">_</span></span><span>           </span><span class="hs-special">[</span><span class="hs-special">]</span><span>     </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">True</span></span><span>
</span><span id="line-141"></span><span>    </span><span class="annot"><a href="#local-6989586621680814683"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span id="local-6989586621680814682"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814682"><span class="hs-identifier hs-var">seen_so_far</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621680814681"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814681"><span class="hs-identifier hs-var">x</span></a></span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span id="local-6989586621680814680"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814680"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">if</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814681"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; Bool
</span><a href="#local-6989586621680814679"><span class="hs-operator hs-var">`is_elem`</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814682"><span class="hs-identifier hs-var">seen_so_far</span></a></span><span>
</span><span id="line-142"></span><span>                           </span><span class="hs-keyword">then</span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">False</span></span><span>
</span><span id="line-143"></span><span>                           </span><span class="hs-keyword">else</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; [a] -&gt; Bool
</span><a href="#local-6989586621680814683"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814681"><span class="hs-identifier hs-var">x</span></a></span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; [a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814682"><span class="hs-identifier hs-var">seen_so_far</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814680"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-144"></span><span>
</span><span id="line-145"></span><span>    </span><span id="local-6989586621680814679"><span class="annot"><span class="annottext">is_elem :: a -&gt; [a] -&gt; Bool
</span><a href="#local-6989586621680814679"><span class="hs-identifier hs-var hs-var">is_elem</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">String -&gt; a -&gt; [a] -&gt; Bool
forall a. Eq a =&gt; String -&gt; a -&gt; [a] -&gt; Bool
</span><a href="GHC.Utils.Misc.html#isIn"><span class="hs-identifier hs-var">isIn</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;hasNoDups&quot;</span></span><span>
</span><span id="line-146"></span><span>
</span><span id="line-147"></span><span id="local-6989586621680814810"><span class="annot"><a href="GHC.Data.List.SetOps.html#equivClasses"><span class="hs-identifier hs-type">equivClasses</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680814810"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814810"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-comment">-- Comparison</span><span>
</span><span id="line-148"></span><span>             </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814810"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-149"></span><span>             </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../base/src/GHC.Base.html#NonEmpty"><span class="hs-identifier hs-type">NonEmpty</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814810"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-150"></span><span>
</span><span id="line-151"></span><span id="equivClasses"><span class="annot"><span class="annottext">equivClasses :: forall a. (a -&gt; a -&gt; Ordering) -&gt; [a] -&gt; [NonEmpty a]
</span><a href="GHC.Data.List.SetOps.html#equivClasses"><span class="hs-identifier hs-var hs-var">equivClasses</span></a></span></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><span class="hs-identifier">_</span></span><span>   </span><span class="hs-special">[</span><span class="hs-special">]</span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-152"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#equivClasses"><span class="hs-identifier hs-var">equivClasses</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><span class="hs-identifier">_</span></span><span>   </span><span class="hs-special">[</span><span id="local-6989586621680814676"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814676"><span class="hs-identifier hs-var">stuff</span></a></span></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814676"><span class="hs-identifier hs-var">stuff</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; NonEmpty a
forall a. a -&gt; [a] -&gt; NonEmpty a
</span><a href="../../base/src/GHC.Base.html#%3A%7C"><span class="hs-operator hs-var">:|</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">]</span><span>
</span><span id="line-153"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#equivClasses"><span class="hs-identifier hs-var">equivClasses</span></a></span><span> </span><span id="local-6989586621680814674"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621680814674"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span id="local-6989586621680814673"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814673"><span class="hs-identifier hs-var">items</span></a></span></span><span>   </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Bool) -&gt; [a] -&gt; [NonEmpty a]
forall (f :: * -&gt; *) a.
Foldable f =&gt;
(a -&gt; a -&gt; Bool) -&gt; f a -&gt; [NonEmpty a]
</span><a href="../../base/src/Data.List.NonEmpty.html#groupBy"><span class="hs-identifier hs-var">NE.groupBy</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814671"><span class="hs-identifier hs-var">eq</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering) -&gt; [a] -&gt; [a]
forall a. (a -&gt; a -&gt; Ordering) -&gt; [a] -&gt; [a]
</span><a href="../../base/src/Data.OldList.html#sortBy"><span class="hs-identifier hs-var">L.sortBy</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621680814674"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814673"><span class="hs-identifier hs-var">items</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-154"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-155"></span><span>    </span><span id="local-6989586621680814671"><span class="annot"><span class="annottext">eq :: a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814671"><span class="hs-identifier hs-var hs-var">eq</span></a></span></span><span> </span><span id="local-6989586621680814669"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814669"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621680814668"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814668"><span class="hs-identifier hs-var">b</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621680814674"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814669"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814668"><span class="hs-identifier hs-var">b</span></a></span><span> </span><span class="hs-keyword">of</span><span> </span><span class="hs-special">{</span><span> </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier hs-var">EQ</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">True</span></span><span class="hs-special">;</span><span> </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">False</span></span><span> </span><span class="hs-special">}</span><span>
</span><span id="line-156"></span><span>
</span><span id="line-157"></span><span id="local-6989586621680814803"><span class="annot"><a href="GHC.Data.List.SetOps.html#removeDups"><span class="hs-identifier hs-type">removeDups</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680814803"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680814803"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-comment">-- Comparison function</span><span>
</span><span id="line-158"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814803"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-159"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814803"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- List with no duplicates</span><span>
</span><span id="line-160"></span><span>               </span><span class="hs-special">[</span><span class="annot"><a href="../../base/src/GHC.Base.html#NonEmpty"><span class="hs-identifier hs-type">NonEmpty</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814803"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span></span><span> </span><span class="hs-comment">-- List of duplicate groups.  One representative</span><span>
</span><span id="line-161"></span><span>                             </span><span class="hs-comment">-- from each group appears in the first result</span><span>
</span><span id="line-162"></span><span>
</span><span id="line-163"></span><span id="removeDups"><span class="annot"><span class="annottext">removeDups :: forall a. (a -&gt; a -&gt; Ordering) -&gt; [a] -&gt; ([a], [NonEmpty a])
</span><a href="GHC.Data.List.SetOps.html#removeDups"><span class="hs-identifier hs-var hs-var">removeDups</span></a></span></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><span class="hs-identifier">_</span></span><span>   </span><span class="hs-special">[</span><span class="hs-special">]</span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-164"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#removeDups"><span class="hs-identifier hs-var">removeDups</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><span class="hs-identifier">_</span></span><span>   </span><span class="hs-special">[</span><span id="local-6989586621680814665"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814665"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814665"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-165"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#removeDups"><span class="hs-identifier hs-var">removeDups</span></a></span><span> </span><span id="local-6989586621680814664"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621680814664"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span id="local-6989586621680814663"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814663"><span class="hs-identifier hs-var">xs</span></a></span></span><span>
</span><span id="line-166"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">([NonEmpty a] -&gt; NonEmpty a -&gt; ([NonEmpty a], a))
-&gt; [NonEmpty a] -&gt; [NonEmpty a] -&gt; ([NonEmpty a], [a])
forall (t :: * -&gt; *) s a b.
Traversable t =&gt;
(s -&gt; a -&gt; (s, b)) -&gt; s -&gt; t a -&gt; (s, t b)
</span><a href="../../base/src/Data.Traversable.html#mapAccumR"><span class="hs-identifier hs-var">L.mapAccumR</span></a></span><span> </span><span class="annot"><span class="annottext">[NonEmpty a] -&gt; NonEmpty a -&gt; ([NonEmpty a], a)
forall a. [NonEmpty a] -&gt; NonEmpty a -&gt; ([NonEmpty a], a)
</span><a href="#local-6989586621680814661"><span class="hs-identifier hs-var">collect_dups</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering) -&gt; [a] -&gt; [NonEmpty a]
forall a. (a -&gt; a -&gt; Ordering) -&gt; [a] -&gt; [NonEmpty a]
</span><a href="GHC.Data.List.SetOps.html#equivClasses"><span class="hs-identifier hs-var">equivClasses</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621680814664"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814663"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">of</span><span> </span><span class="hs-special">{</span><span> </span><span class="hs-special">(</span><span id="local-6989586621680814660"><span class="annot"><span class="annottext">[NonEmpty a]
</span><a href="#local-6989586621680814660"><span class="hs-identifier hs-var">dups</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680814659"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814659"><span class="hs-identifier hs-var">xs'</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span>
</span><span id="line-167"></span><span>    </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814659"><span class="hs-identifier hs-var">xs'</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[NonEmpty a]
</span><a href="#local-6989586621680814660"><span class="hs-identifier hs-var">dups</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">}</span><span>
</span><span id="line-168"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-169"></span><span>    </span><span id="local-6989586621680814797"><span class="annot"><a href="#local-6989586621680814661"><span class="hs-identifier hs-type">collect_dups</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../base/src/GHC.Base.html#NonEmpty"><span class="hs-identifier hs-type">NonEmpty</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814797"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#NonEmpty"><span class="hs-identifier hs-type">NonEmpty</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814797"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="annot"><a href="../../base/src/GHC.Base.html#NonEmpty"><span class="hs-identifier hs-type">NonEmpty</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814797"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621680814797"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span><span>
</span><span id="line-170"></span><span>    </span><span id="local-6989586621680814661"><span class="annot"><span class="annottext">collect_dups :: forall a. [NonEmpty a] -&gt; NonEmpty a -&gt; ([NonEmpty a], a)
</span><a href="#local-6989586621680814661"><span class="hs-identifier hs-var hs-var">collect_dups</span></a></span></span><span> </span><span id="local-6989586621680814658"><span class="annot"><span class="annottext">[NonEmpty a]
</span><a href="#local-6989586621680814658"><span class="hs-identifier hs-var">dups_so_far</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621680814657"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814657"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#%3A%7C"><span class="hs-operator hs-type">:|</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span>     </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[NonEmpty a]
</span><a href="#local-6989586621680814658"><span class="hs-identifier hs-var">dups_so_far</span></a></span><span class="hs-special">,</span><span>      </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814657"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-171"></span><span>    </span><span class="annot"><a href="#local-6989586621680814661"><span class="hs-identifier hs-var">collect_dups</span></a></span><span> </span><span id="local-6989586621680814656"><span class="annot"><span class="annottext">[NonEmpty a]
</span><a href="#local-6989586621680814656"><span class="hs-identifier hs-var">dups_so_far</span></a></span></span><span> </span><span id="local-6989586621680814655"><span class="annot"><span class="annottext">dups :: NonEmpty a
</span><a href="#local-6989586621680814655"><span class="hs-identifier hs-var">dups</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span id="local-6989586621680814654"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814654"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#%3A%7C"><span class="hs-operator hs-type">:|</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><span class="hs-identifier">_</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">NonEmpty a
</span><a href="#local-6989586621680814655"><span class="hs-identifier hs-var">dups</span></a></span><span class="annot"><span class="annottext">NonEmpty a -&gt; [NonEmpty a] -&gt; [NonEmpty a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span class="annot"><span class="annottext">[NonEmpty a]
</span><a href="#local-6989586621680814656"><span class="hs-identifier hs-var">dups_so_far</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814654"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-172"></span><span>
</span><span id="line-173"></span><span id="local-6989586621680814795"><span class="annot"><a href="GHC.Data.List.SetOps.html#findDupsEq"><span class="hs-identifier hs-type">findDupsEq</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680814795"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-glyph">-&gt;</span><span class="annot"><a href="#local-6989586621680814795"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-glyph">-&gt;</span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680814795"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../base/src/GHC.Base.html#NonEmpty"><span class="hs-identifier hs-type">NonEmpty</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680814795"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-174"></span><span id="findDupsEq"><span class="annot"><span class="annottext">findDupsEq :: forall a. (a -&gt; a -&gt; Bool) -&gt; [a] -&gt; [NonEmpty a]
</span><a href="GHC.Data.List.SetOps.html#findDupsEq"><span class="hs-identifier hs-var hs-var">findDupsEq</span></a></span></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><span class="hs-identifier">_</span></span><span>  </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-175"></span><span class="annot"><a href="GHC.Data.List.SetOps.html#findDupsEq"><span class="hs-identifier hs-var">findDupsEq</span></a></span><span> </span><span id="local-6989586621680814652"><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814652"><span class="hs-identifier hs-var">eq</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621680814651"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814651"><span class="hs-identifier hs-var">x</span></a></span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span id="local-6989586621680814650"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814650"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; Bool
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#null"><span class="hs-identifier hs-var">L.null</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814648"><span class="hs-identifier hs-var">eq_xs</span></a></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Bool) -&gt; [a] -&gt; [NonEmpty a]
forall a. (a -&gt; a -&gt; Bool) -&gt; [a] -&gt; [NonEmpty a]
</span><a href="GHC.Data.List.SetOps.html#findDupsEq"><span class="hs-identifier hs-var">findDupsEq</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814652"><span class="hs-identifier hs-var">eq</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814650"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-176"></span><span>                     </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>     </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814651"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; NonEmpty a
forall a. a -&gt; [a] -&gt; NonEmpty a
</span><a href="../../base/src/GHC.Base.html#%3A%7C"><span class="hs-operator hs-var">:|</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814648"><span class="hs-identifier hs-var">eq_xs</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">NonEmpty a -&gt; [NonEmpty a] -&gt; [NonEmpty a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Bool) -&gt; [a] -&gt; [NonEmpty a]
forall a. (a -&gt; a -&gt; Bool) -&gt; [a] -&gt; [NonEmpty a]
</span><a href="GHC.Data.List.SetOps.html#findDupsEq"><span class="hs-identifier hs-var">findDupsEq</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814652"><span class="hs-identifier hs-var">eq</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814647"><span class="hs-identifier hs-var">neq_xs</span></a></span><span>
</span><span id="line-177"></span><span>    </span><span class="hs-keyword">where</span><span> </span><span class="hs-special">(</span><span id="local-6989586621680814648"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814648"><span class="hs-identifier hs-var">eq_xs</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680814647"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814647"><span class="hs-identifier hs-var">neq_xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; Bool) -&gt; [a] -&gt; ([a], [a])
forall a. (a -&gt; Bool) -&gt; [a] -&gt; ([a], [a])
</span><a href="../../base/src/Data.OldList.html#partition"><span class="hs-identifier hs-var">L.partition</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; a -&gt; Bool
</span><a href="#local-6989586621680814652"><span class="hs-identifier hs-var">eq</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680814651"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680814650"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-178"></span></pre></body></html>